/*
 * @Autor: taobo
 * @Date: 2020-06-14 23:26:54
 * @LastEditTime: 2020-06-15 13:05:34
 * @Description: file content
 */ 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    bool helper_1(const string& s,int st,const string& p, int ps){ //回溯法
        if(ps==p.length())
            return st==s.length();
        bool firstmatch = (s.length()!=st) && ((s[st]==p[ps])||(p[ps]=='.'));
        if(ps+1<p.length() && p[ps+1]=='*'){//pattern zero/one
            return helper_1(s,st,p,ps+2)||(firstmatch && helper_1(s, st+1, p, ps));
        }else{//pattern
            return firstmatch && helper_1(s, st+1, p, ps+1);
        }
    }
    bool helper_2(const string& s,int st,const string& p, int ps,vector<vector<int>>& memo){//回溯+剪枝
        if(memo[st][ps]!=0){
            return memo[st][ps]==1;
        }
        bool ans = false;
        if(ps==p.length())
            ans = st==s.length();
        else{
            bool firstmatch = (s.length()!=st) && ((s[st]==p[ps])||(p[ps]=='.'));
            if(ps+1<p.length() && p[ps+1]=='*'){//pattern zero/one
                ans =  helper_2(s,st,p,ps+2,memo)||(firstmatch && helper_2(s, st+1, p, ps,memo));
            }else{//pattern
                ans =  firstmatch && helper_2(s, st+1, p, ps+1,memo);
            }
        }
        memo[st][ps] = ans ? 1 : 2;
        return ans;
    }
    bool isMatch(const string& s,const string& p) {
        vector<vector<int>> memo(s.length()+1,vector<int>(p.length()+1,0));
        bool ans1 = helper_1(s,0,p,0);
        bool ans2 = helper_2(s,0,p,0,memo);
        return ans1==ans2;
    }
};





int main()
{
        string s = "aaaaaaaaaaaaab";
        string p = "a*a*a*a*a*a*a*a*a*a*c";
        Solution obj;
        cout << boolalpha << obj.isMatch(s,p) << '\n';
        return 0;
}